package com.example.system.class13;

/**
 * @Date 2022/8/6
 * @Author Jonathan
 * @Description 最低公共祖先
 */
public class Code08_CommonLowerAncestor {
    public static void main(String[] args) {
        System.out.println("hello world");
        //lowerAncestor()
    }


    // for test 来个对数器

    public static Node lowerAncestor(Node root, Node a, Node b) {
        return process(root, a, b).ans;
    }


    public static Info process(Node x, Node a, Node b) {
        if (x == null) {
            return new Info(false, false, null);
        }
        final Info left = process(x.left, a, b);
        final Info right = process(x.right, a, b);
        boolean findA = (x == a) || left.findA || right.findA;
        boolean findB = (x == b) || left.findB || right.findB;
        Node ans = null;
        if (left.ans != null) {
            ans = left.ans;
        } else if (right.ans != null) {
            ans = right.ans;
        } else if (findA && findB) {
            // 在当前节点第一次发现
            ans = x;
        }
        return new Info(findA, findB, ans);
    }


    static class Info {
        private boolean findA;
        private boolean findB;
        private Node ans;


        public Info(boolean findA, boolean findB, Node ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }

    }
}
